package org.basis.algorithm.practice;

import lombok.Data;

import java.util.HashMap;
import java.util.LinkedList;

/**
 * 求树的最大高度和宽度
 *
 * @author Mr_wenpan@163.com 2022/03/23 10:38
 */
public class TreeHeightAndWidth {

    public static void main(String[] args) {

    }

    public static int width(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }
        //队列
        LinkedList<TreeNode> queue = new LinkedList<>();
        // 存放层级关系的map
        HashMap<TreeNode, Integer> levelMap = new HashMap<>();
        // 树的最大宽度
        int maxWidth = -1;
        // 当前所在的层
        int currentLevel = 1;
        // 当前层的节点数量
        int currentLevelCount = 0;
        queue.addLast(treeNode);
        // 先记录上每个节点所处的层
        levelMap.put(treeNode, 1);

        while (!queue.isEmpty()) {
            TreeNode poll = queue.pollFirst();
            // 节点没有跨层
            if (currentLevel == levelMap.get(poll)) {
                currentLevelCount++;
            } else {
                // 遇到第一个跨层的节点，先【结算上一层】节点个数和最大值，然后【重置当前层的节点个数为1个】
                maxWidth = Math.max(maxWidth, currentLevelCount);
                currentLevelCount = 1;
                currentLevel++;
            }
            // 左右孩子分别入队列，并记录他们所处的层数
            if (poll.left != null) {
                levelMap.put(poll.left, levelMap.get(poll) + 1);
                queue.addLast(poll.left);
            }
            if (poll.right != null) {
                levelMap.put(poll.right, levelMap.get(poll) + 1);
                queue.addLast(poll.right);
            }
        }

        return maxWidth;
    }

    /**
     * 以宽度优先求二叉树的高度
     * 该二叉树有多少层，那么就说明该树有多高，根据这个特性我们就可以使用宽度优先遍历来计算该树的层数，进而求得树的高度
     */
    public static int height2(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        HashMap<TreeNode, Integer> levelMap = new HashMap<>();
        // 当前层
        int currentLevel = 1;
        queue.addLast(treeNode);
        levelMap.put(treeNode, 1);

        while (!queue.isEmpty()) {
            TreeNode poll = queue.pollFirst();

            // 节点出现了跨层
            if (currentLevel != levelMap.get(poll)) {
                currentLevel++;
            }

            // 处理孩子节点
            if (poll.left != null) {
                levelMap.put(poll.left, levelMap.get(poll) + 1);
                queue.addLast(poll.left);
            }
            if (poll.right != null) {
                levelMap.put(poll.right, levelMap.get(poll) + 1);
                queue.addLast(poll.right);
            }
        }

        return currentLevel;
    }

    /**
     * 以深度优先，求二叉树的高度
     */
    public static int height(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }
        // 分别获取到左右孩子的树高度（问左右孩子要信息）
        int left = height(treeNode.left);
        int right = height(treeNode.right);

        // 整合所有孩子的高度，以当前节点为头的二叉树的树高为左右孩子中最高的高度 + 1
        return Math.max(left, right) + 1;
    }


    @Data
    static class TreeNode {
        String val;
        TreeNode left;
        TreeNode right;

        public TreeNode(String val) {
            this.val = val;
        }
    }
}
